#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 线索二叉树结点结构
typedef struct ThreadNode
{
    char data;                          // 结点数据
    struct ThreadNode *lchild, *rchild; // 左右孩子指针
    int ltag, rtag;                     // 线索标记 (0:孩子, 1:线索)
} ThreadNode, *ThreadTree;

// 全局变量 - 指向前驱结点
ThreadNode *pre = NULL;

// 初始化二叉树
void InitTree(ThreadTree &T)
{
    T = NULL;   // 初始化为空树
    pre = NULL; // 重置前驱指针
}

// 创建新结点
ThreadNode *CreateNode(char data)
{
    ThreadNode *node = (ThreadNode *)malloc(sizeof(ThreadNode));
    if (!node)
    {
        printf("Memory allocation failed\n");
        exit(1);
    }
    node->data = data;
    node->lchild = node->rchild = NULL;
    node->ltag = node->rtag = 0; // 初始标记为孩子
    return node;
}

// 构建示例二叉树
/*
        A
       / \
      B   C
     / \   \
    D   E   F
*/
ThreadTree BuildSampleTree()
{
    ThreadNode *A = CreateNode('A');
    ThreadNode *B = CreateNode('B');
    ThreadNode *C = CreateNode('C');
    ThreadNode *D = CreateNode('D');
    ThreadNode *E = CreateNode('E');
    ThreadNode *F = CreateNode('F');

    A->lchild = B;
    A->rchild = C;
    B->lchild = D;
    B->rchild = E;
    C->rchild = F;

    return A;
}

// 中序线索化二叉树
void InThread(ThreadTree p)
{
    if (p)
    {
        // 递归线索化左子树
        InThread(p->lchild);

        // 处理当前结点
        if (!p->lchild)
        {                    // 左孩子为空
            p->ltag = 1;     // 设置左线索标记
            p->lchild = pre; // 左指针指向前驱
        }

        if (pre && !pre->rchild)
        {                    // 前驱结点存在且右孩子为空
            pre->rtag = 1;   // 设置前驱的右线索标记
            pre->rchild = p; // 前驱的右指针指向当前结点
        }

        pre = p; // 更新前驱为当前结点

        // 递归线索化右子树
        InThread(p->rchild);
    }
}

// 创建头结点并线索化二叉树
void CreateInorderThread(ThreadTree &Thrt, ThreadTree T)
{
    // 创建头结点
    Thrt = (ThreadNode *)malloc(sizeof(ThreadNode));
    if (!Thrt)
    {
        printf("Memory allocation failed\n");
        exit(1);
    }

    // 设置头结点
    Thrt->ltag = 0;      // 左标记为孩子
    Thrt->rtag = 1;      // 右标记为线索
    Thrt->rchild = Thrt; // 右指针指向自己

    if (!T)
    { // 空树
        Thrt->lchild = Thrt;
    }
    else
    {
        Thrt->lchild = T; // 头结点左孩子指向根结点
        pre = Thrt;       // 初始化前驱为头结点

        // 中序线索化
        InThread(T);

        // 处理最后一个结点
        pre->rtag = 1;      // 最后一个结点右标记为线索
        pre->rchild = Thrt; // 最后一个结点指向头结点

        // 头结点右线索指向最后一个结点
        Thrt->rchild = pre;
    }
}

// 中序遍历线索二叉树
void InorderTraversal(ThreadTree Thrt)
{
    ThreadNode *p = Thrt->lchild; // 从根结点开始

    // 遍历到最左下结点
    while (p != Thrt)
    {
        while (p->ltag == 0)
        { // 找中序序列的第一个结点
            p = p->lchild;
        }

        printf("%c ", p->data); // 访问结点

        // 沿右线索访问后继结点
        while (p->rtag == 1 && p->rchild != Thrt)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }

        // 转向右子树
        p = p->rchild;
    }
    printf("\n");
}

// 查找中序前驱
ThreadNode *FindPredecessor(ThreadNode *p)
{
    if (p->ltag == 1)
    { // 有左线索
        return p->lchild;
    }

    // 没有左线索，前驱在左子树的最右下结点
    ThreadNode *pre = p->lchild;
    while (pre->rtag == 0)
    {
        pre = pre->rchild;
    }
    return pre;
}

// 查找中序后继
ThreadNode *FindSuccessor(ThreadNode *p)
{
    if (p->rtag == 1)
    { // 有右线索
        return p->rchild;
    }

    // 没有右线索，后继在右子树的最左下结点
    ThreadNode *suc = p->rchild;
    while (suc->ltag == 0)
    {
        suc = suc->lchild;
    }
    return suc;
}

// 销毁线索二叉树
void DestroyTree(ThreadTree &Thrt)
{
    if (Thrt)
    {
        // 遍历解除线索并释放结点
        ThreadNode *p = Thrt->lchild;
        ThreadNode *temp;

        while (p != Thrt)
        {
            while (p->ltag == 0)
            {
                p = p->lchild;
            }

            temp = p;

            // 解除右线索
            if (p->rtag == 1)
            {
                p = p->rchild;
            }
            else
            {
                p = p->rchild;
                while (p->ltag == 0)
                {
                    p = p->lchild;
                }
            }

            // 恢复原始指针（可选）
            if (temp->ltag == 1)
                temp->lchild = NULL;
            if (temp->rtag == 1)
                temp->rchild = NULL;

            free(temp);
        }

        free(Thrt); // 释放头结点
        Thrt = NULL;
    }
}

int main()
{
    ThreadTree T = NULL;
    ThreadTree Thrt = NULL; // 头结点指针

    // 初始化树
    InitTree(T);

    // 构建二叉树
    T = BuildSampleTree();
    printf("Binary tree structure:\n");
    printf("        A\n       / \\\n      B   C\n     / \\   \\\n    D   E   F\n\n");

    // 创建线索二叉树
    CreateInorderThread(Thrt, T);
    printf("Inorder threading completed\n");

    // 中序遍历
    printf("Inorder traversal: ");
    InorderTraversal(Thrt); // D B E A C F

    // 查找前驱和后继
    ThreadNode *node = T; // 根结点A

    // 查找A的前驱和后继
    ThreadNode *pred = FindPredecessor(node);
    ThreadNode *succ = FindSuccessor(node);
    printf("Node '%c': Predecessor is '%c', Successor is '%c'\n",
           node->data, pred->data, succ->data);

    // 查找B的前驱和后继
    node = T->lchild; // 结点B
    pred = FindPredecessor(node);
    succ = FindSuccessor(node);
    printf("Node '%c': Predecessor is '%c', Successor is '%c'\n",
           node->data, pred->data, succ->data);

    // 查找F的前驱和后继
    node = T->rchild->rchild; // 结点F
    pred = FindPredecessor(node);
    succ = FindSuccessor(node);
    printf("Node '%c': Predecessor is '%c', Successor is '%c' (head node)\n",
           node->data, pred->data, succ->data);

    // 销毁树
    DestroyTree(Thrt);
    printf("Tree destroyed\n");

    return 0;
}